<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 6.3.0">
  <link rel="apple-touch-icon" sizes="180x180" href="/xlrblog/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/xlrblog/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/xlrblog/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/xlrblog/images/logo.svg" color="#222">

<link rel="stylesheet" href="/xlrblog/css/main.css">


<link rel="stylesheet" href="/xlrblog/lib/font-awesome/css/all.min.css">

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"gitee.com","root":"/xlrblog/","scheme":"Pisces","version":"7.8.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":true,"show_result":true,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.json"};
  </script>

  <meta name="description" content="蓝桥杯的一些练习题 数字三角形(简单)题目描述数字三角形 - 蓝桥云课 (lanqiao.cn)   上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。 路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。 输入描述输入的第一行">
<meta property="og:type" content="article">
<meta property="og:title" content="蓝桥杯部分题目">
<meta property="og:url" content="https://gitee.com/xlr0306/2023/01/06/%E8%93%9D%E6%A1%A5%E6%9D%AF%E9%83%A8%E5%88%86%E9%A2%98%E7%9B%AE/index.html">
<meta property="og:site_name" content="君不见的博客">
<meta property="og:description" content="蓝桥杯的一些练习题 数字三角形(简单)题目描述数字三角形 - 蓝桥云课 (lanqiao.cn)   上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。 路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。 输入描述输入的第一行">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://note.youdao.com/yws/api/personal/file/WEB43f0822f4c09bb656e8fb993eb8c4d51?method=download&shareKey=c65f97994f618d17eaed559719c3329a">
<meta property="og:image" content="https://note.youdao.com/yws/api/personal/file/WEB10001394df5976a0891b51ff0bbb9545?method=download&shareKey=2b18f242ed67fd3c0162877fa7e5c174">
<meta property="article:published_time" content="2023-01-06T12:05:12.000Z">
<meta property="article:modified_time" content="2023-04-07T14:01:19.915Z">
<meta property="article:author" content="君不见">
<meta property="article:tag" content="Note">
<meta property="article:tag" content="Practices">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://note.youdao.com/yws/api/personal/file/WEB43f0822f4c09bb656e8fb993eb8c4d51?method=download&shareKey=c65f97994f618d17eaed559719c3329a">

<link rel="canonical" href="https://gitee.com/xlr0306/2023/01/06/%E8%93%9D%E6%A1%A5%E6%9D%AF%E9%83%A8%E5%88%86%E9%A2%98%E7%9B%AE/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>蓝桥杯部分题目 | 君不见的博客</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/xlrblog/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">君不见的博客</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
      <p class="site-subtitle" itemprop="description">记录生活中的点点滴滴</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/xlrblog/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/xlrblog/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/xlrblog/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/xlrblog/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div id="search-result">
  <div id="no-result">
    <i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
  </div>
</div>

    </div>
  </div>

</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content post posts-expand">
            

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://gitee.com/xlr0306/2023/01/06/%E8%93%9D%E6%A1%A5%E6%9D%AF%E9%83%A8%E5%88%86%E9%A2%98%E7%9B%AE/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/xlrblog/images/avatar.gif">
      <meta itemprop="name" content="君不见">
      <meta itemprop="description" content="君不见，黄河之水天上来，奔流到海不复回。">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="君不见的博客">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          蓝桥杯部分题目
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>

              <time title="创建时间：2023-01-06 20:05:12" itemprop="dateCreated datePublished" datetime="2023-01-06T20:05:12+08:00">2023-01-06</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="far fa-calendar-check"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2023-04-07 22:01:19" itemprop="dateModified" datetime="2023-04-07T22:01:19+08:00">2023-04-07</time>
              </span>
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-folder"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/xlrblog/categories/algorithm/" itemprop="url" rel="index"><span itemprop="name">algorithm</span></a>
                </span>
            </span>

          

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <p>蓝桥杯的一些练习题</p>
<h2 id="数字三角形-简单"><a href="#数字三角形-简单" class="headerlink" title="数字三角形(简单)"></a>数字三角形(简单)</h2><h3 id="题目描述"><a href="#题目描述" class="headerlink" title="题目描述"></a>题目描述</h3><p><a target="_blank" rel="noopener" href="https://www.lanqiao.cn/problems/505/learning/">数字三角形 - 蓝桥云课 (lanqiao.cn)</a> </p>
<p><img src="https://note.youdao.com/yws/api/personal/file/WEB43f0822f4c09bb656e8fb993eb8c4d51?method=download&shareKey=c65f97994f618d17eaed559719c3329a" alt="图片描述"></p>
<p>上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。</p>
<p>路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。</p>
<h3 id="输入描述"><a href="#输入描述" class="headerlink" title="输入描述"></a>输入描述</h3><p>输入的第一行包含一个整数 N (1≤N≤100)，表示三角形的行数。</p>
<p>下面的 N 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。</p>
<h3 id="输出描述"><a href="#输出描述" class="headerlink" title="输出描述"></a>输出描述</h3><p>输出一个整数，表示答案。</p>
<h3 id="输入输出样例"><a href="#输入输出样例" class="headerlink" title="输入输出样例"></a>输入输出样例</h3><h4 id="示例"><a href="#示例" class="headerlink" title="示例"></a>示例</h4><blockquote>
<p>输入</p>
</blockquote>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">5</span><br><span class="line">7</span><br><span class="line">3 8</span><br><span class="line">8 1 0</span><br><span class="line">2 7 4 4</span><br><span class="line">4 5 2 6 5</span><br></pre></td></tr></table></figure>

<blockquote>
<p>输出</p>
</blockquote>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">27</span><br></pre></td></tr></table></figure>

<h3 id="运行限制"><a href="#运行限制" class="headerlink" title="运行限制"></a>运行限制</h3><ul>
<li>最大运行时间：1s</li>
<li>最大运行内存: 256M</li>
</ul>
<h3 id="题解"><a href="#题解" class="headerlink" title="题解"></a>题解</h3><p>关于向左向右步数不能相差1的理解：</p>
<p>说明最后在最后一层一定会落到<strong>中间</strong>,所以只需判断最后一层。</p>
<p>最后一层为奇数：中位数</p>
<p>最后一层偶数：中间两个取最大</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="type">int</span> num[<span class="number">200</span>][<span class="number">200</span>],n,ans;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">  cin &gt;&gt; n;</span><br><span class="line">  <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>;i &lt;= n;i++) &#123;</span><br><span class="line">	  <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">1</span>;j &lt;= i;j++) &#123;</span><br><span class="line">	      cin &gt;&gt; num[i][j];</span><br><span class="line">		  num[i][j] += <span class="built_in">max</span>(num[i<span class="number">-1</span>][j],num[i<span class="number">-1</span>][j<span class="number">-1</span>]);</span><br><span class="line">	  &#125;</span><br><span class="line">  &#125;</span><br><span class="line">  ans = <span class="built_in">max</span>(num[n][(n+<span class="number">1</span>)/<span class="number">2</span>],num[n][(n+<span class="number">2</span>)/<span class="number">2</span>]);</span><br><span class="line">  cout &lt;&lt; ans;</span><br><span class="line">  <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="排序-简单）"><a href="#排序-简单）" class="headerlink" title="排序(简单）"></a>排序(简单）</h2><h3 id="题目描述-1"><a href="#题目描述-1" class="headerlink" title="题目描述"></a>题目描述</h3><p><a target="_blank" rel="noopener" href="https://www.lanqiao.cn/problems/598/learning/">排序 - 蓝桥云课 (lanqiao.cn)</a> </p>
<p><strong>本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。</strong></p>
<p>小蓝最近学习了一些排序算法，其中冒泡排序让他印象深刻。</p>
<p>在冒泡排序中，每次只能交换相邻的两个元素。</p>
<p>小蓝发现，如果对一个字符串中的字符排序，只允许交换相邻的两个字符， 则在所有可能的排序方案中，冒泡排序的总交换次数是最少的。</p>
<p>例如，对于字符串 lan 排序，只需要 1 次交换。对于字符串 qiao 排序，总共需要 4次交换。</p>
<p>小蓝找到了很多字符串试图排序，他恰巧碰到一个字符串，需要 100 次交 换，可是他忘了吧这个字符串记下来，现在找不到了。</p>
<p>请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串，对 该串的字符排序，正好需要 100 次交换。如果可能找到多个，请告诉小蓝最短的那个。如果最短的仍然有多个，请告诉小蓝字典序最小的那个。</p>
<h3 id="运行限制-1"><a href="#运行限制-1" class="headerlink" title="运行限制"></a>运行限制</h3><ul>
<li>最大运行时间：1s</li>
<li>最大运行内存: 128M</li>
</ul>
<h3 id="题解-1"><a href="#题解-1" class="headerlink" title="题解"></a>题解</h3><p>对于<strong>完全乱序时的</strong>N个字母的字符串，最多需要交换N*(N-1)&#x2F;2次 </p>
<p>当N&#x3D;15时，有15*14&#x2F;2&#x3D;105，即满足100次交换所需的最短字符串有15个字母。 </p>
<p>要求字典序最小，那么显然要取a~o这15个字典序最小的字母 </p>
<p>逆向思考，目标字符串经过100次交换后，得到正序字符串abcdefghijklmno，而完全逆序的字符串onmlkjihgfedcba变成正序字符串需要105次交换，那么将完全逆序的字符串交换5次后，便能得到答案。</p>
<p>而要求字典序最小，那么将j交换5次提到字符串最前面，就得到了最小的情况</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">  cout &lt;&lt; <span class="string">&quot;jonmlkihgfedcba&quot;</span>;</span><br><span class="line">  <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="杨辉三角形-中等"><a href="#杨辉三角形-中等" class="headerlink" title="杨辉三角形(中等)"></a>杨辉三角形(中等)</h2><h3 id="题目描述-2"><a href="#题目描述-2" class="headerlink" title="题目描述"></a>题目描述</h3><p><a target="_blank" rel="noopener" href="https://www.lanqiao.cn/problems/1457/learning/">杨辉三角形 - 蓝桥云课 (lanqiao.cn)</a> </p>
<p>下面的图形是著名的杨辉三角形：</p>
<p><img src="https://note.youdao.com/yws/api/personal/file/WEB10001394df5976a0891b51ff0bbb9545?method=download&shareKey=2b18f242ed67fd3c0162877fa7e5c174" alt="image"></p>
<p>如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列： 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,⋯</p>
<p>给定一个正整数 NN，请你输出数列中第一次出现 NN 是在第几个数？</p>
<h3 id="输入描述-1"><a href="#输入描述-1" class="headerlink" title="输入描述"></a>输入描述</h3><p>输入一个整数 NN。</p>
<h3 id="输出描述-1"><a href="#输出描述-1" class="headerlink" title="输出描述"></a>输出描述</h3><p>输出一个整数代表答案。</p>
<h3 id="输入输出样例-1"><a href="#输入输出样例-1" class="headerlink" title="输入输出样例"></a>输入输出样例</h3><h4 id="示例-1"><a href="#示例-1" class="headerlink" title="示例 1"></a>示例 1</h4><blockquote>
<p>输入</p>
</blockquote>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">6</span><br></pre></td></tr></table></figure>

<blockquote>
<p>输出</p>
</blockquote>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">13</span><br></pre></td></tr></table></figure>

<h3 id="评测用例规模与约定"><a href="#评测用例规模与约定" class="headerlink" title="评测用例规模与约定"></a>评测用例规模与约定</h3><p>对于 %20 的评测用例，1≤N≤10； 对于所有评测用例，1≤N≤1000000000。</p>
<h3 id="运行限制-2"><a href="#运行限制-2" class="headerlink" title="运行限制"></a>运行限制</h3><ul>
<li>最大运行时间：1s</li>
<li>最大运行内存: 256M</li>
</ul>
<h3 id="题解-2"><a href="#题解-2" class="headerlink" title="题解"></a>题解</h3><p>杨辉三角对称，因此我们只要算一半的数即可(算全部的TLE)，用两个数组维护上一状态和这一状态的数 。</p>
<p>另外还要注意数据范围。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="type">long</span> <span class="type">long</span> a[<span class="number">100025</span>],b[<span class="number">100025</span>];</span><br><span class="line"><span class="comment">//开两个数组，一个保存上一行那一半的数，一个保存目的行那一半的数</span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">  <span class="type">long</span> <span class="type">long</span> n,cnt;</span><br><span class="line">  cin &gt;&gt; n;</span><br><span class="line">  <span class="keyword">if</span>(n == <span class="number">1</span>) &#123;</span><br><span class="line">      cout &lt;&lt; <span class="number">1</span>;</span><br><span class="line">      <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">  &#125;</span><br><span class="line">  a[<span class="number">0</span>] = b[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line">  <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">3</span>;i &lt;= <span class="number">44723</span>;i++) &#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">1</span>;j &lt;= i/<span class="number">2</span>;j++) &#123;</span><br><span class="line">      <span class="keyword">if</span>(j == i/<span class="number">2</span> &amp;&amp; i%<span class="number">2</span> == <span class="number">1</span>) &#123;</span><br><span class="line">        <span class="comment">//如果行数为奇数那么就有个中间数，就是上一行前面数的两倍</span></span><br><span class="line">        b[j] = a[j<span class="number">-1</span>]*<span class="number">2</span>;</span><br><span class="line">      &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">        b[j] = a[j<span class="number">-1</span>] + a[j];<span class="comment">//杨辉三角</span></span><br><span class="line">      &#125;</span><br><span class="line">      <span class="keyword">if</span>(b[j] == n) &#123;</span><br><span class="line">        cnt = i*(i<span class="number">-1</span>)/<span class="number">2</span>+j+<span class="number">1</span>;</span><br><span class="line">        <span class="keyword">goto</span> next;</span><br><span class="line">      &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//更新a数组</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">1</span>;j &lt;= i/<span class="number">2</span>;j++) &#123;</span><br><span class="line">      a[j] = b[j];</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line">  cnt = n*(n+<span class="number">1</span>)/<span class="number">2</span>+<span class="number">2</span>;<span class="comment">//防止溢出</span></span><br><span class="line">  next:</span><br><span class="line">  cout &lt;&lt; cnt &lt;&lt; endl;</span><br><span class="line">  <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="跑步锻炼"><a href="#跑步锻炼" class="headerlink" title="跑步锻炼"></a>跑步锻炼</h2><h3 id="题目描述-3"><a href="#题目描述-3" class="headerlink" title="题目描述"></a>题目描述</h3><p><a target="_blank" rel="noopener" href="https://www.lanqiao.cn/problems/597/learning/">跑步锻炼 - 蓝桥云课 (lanqiao.cn)</a> </p>
<p><strong>本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。</strong></p>
<p>小蓝每天都锻炼身体。</p>
<p>正常情况下，小蓝每天跑 1 千米。如果某天是周一或者月初（1日），为了激励自己，小蓝要跑 22千米。如果同时是周一或月初，小蓝也是跑 2 千米。</p>
<p>小蓝跑步已经坚持了很长时间，从 2000 年 1 月 1 日周六（含）到 2020 年 10 月 1 日周四（含）。请问这段时间小蓝总共跑步多少千米？</p>
<h3 id="运行限制-3"><a href="#运行限制-3" class="headerlink" title="运行限制"></a>运行限制</h3><ul>
<li>最大运行时间：1s</li>
<li>最大运行内存: 128M</li>
</ul>
<h3 id="题解-3"><a href="#题解-3" class="headerlink" title="题解"></a>题解</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">bool</span> <span class="title">isLeap</span><span class="params">(<span class="type">int</span> n)</span> </span>&#123;</span><br><span class="line">  <span class="keyword">return</span> ((n%<span class="number">4</span>==<span class="number">0</span>&amp;&amp;n%<span class="number">100</span>!=<span class="number">0</span>)||n%<span class="number">400</span>==<span class="number">0</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">  <span class="type">int</span> month[]=&#123;<span class="number">0</span>,<span class="number">31</span>,<span class="number">28</span>,<span class="number">31</span>,<span class="number">30</span>,<span class="number">31</span>,<span class="number">30</span>,<span class="number">31</span>,<span class="number">31</span>,<span class="number">30</span>,<span class="number">31</span>,<span class="number">30</span>,<span class="number">31</span>&#125;;</span><br><span class="line">  <span class="type">int</span> week = <span class="number">6</span>;</span><br><span class="line">  <span class="type">int</span> ans = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">2000</span>;i &lt;= <span class="number">2020</span>;i++) &#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">1</span>;j &lt;= <span class="number">12</span>;j++) &#123;</span><br><span class="line">      <span class="keyword">if</span>(<span class="built_in">isLeap</span>(i)) &#123;</span><br><span class="line">        month[<span class="number">2</span>] = <span class="number">29</span>;</span><br><span class="line">      &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">        month[<span class="number">2</span>] = <span class="number">28</span>;</span><br><span class="line">      &#125;</span><br><span class="line">      <span class="keyword">for</span>(<span class="type">int</span> k = <span class="number">1</span>;k &lt;= month[j];k++) &#123;</span><br><span class="line">        ans++;</span><br><span class="line">        <span class="keyword">if</span>(week &gt; <span class="number">7</span>) &#123;</span><br><span class="line">          week = <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(week == <span class="number">1</span> || k == <span class="number">1</span>) &#123;  <span class="comment">//判断周一和每月的一号</span></span><br><span class="line">          ans++;</span><br><span class="line">        &#125;</span><br><span class="line">        week++;</span><br><span class="line">        <span class="keyword">if</span>(i == <span class="number">2020</span> &amp;&amp; j == <span class="number">10</span> &amp;&amp; k == <span class="number">1</span>) &#123;</span><br><span class="line">          cout &lt;&lt; ans;</span><br><span class="line">          <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">      &#125;</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line">  </span><br><span class="line">  <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="小明的彩灯-简单"><a href="#小明的彩灯-简单" class="headerlink" title="小明的彩灯(简单)"></a>小明的彩灯(简单)</h2><h3 id="题目描述-4"><a href="#题目描述-4" class="headerlink" title="题目描述"></a>题目描述</h3><p><a target="_blank" rel="noopener" href="https://www.lanqiao.cn/problems/1276/learning/">小明的彩灯 - 蓝桥云课 (lanqiao.cn)</a> </p>
<p>小明拥有 N 个彩灯，第 i 个彩灯的初始亮度为 ai。</p>
<p>小明将进行 Q 次操作，每次操作可选择一段区间，并使区间内彩灯的亮度 +x（x 可能为负数）。</p>
<p>求 Q 次操作后每个彩灯的亮度（若彩灯亮度为负数则输出 0）。</p>
<h3 id="输入描述-2"><a href="#输入描述-2" class="headerlink" title="输入描述"></a>输入描述</h3><p>第一行包含两个正整数 N，Q分别表示彩灯的数量和操作的次数。</p>
<p>第二行包含 NN 个整数，表示彩灯的初始亮度。</p>
<p>接下来 Q 行每行包含一个操作，格式如下：</p>
<p><code>l r x</code>，表示将区间 l∼r 的彩灯的亮度 +x。</p>
<p>1≤N,Q≤5×10^5，0≤ai≤10^9，1≤l≤r≤N，−10^9≤x≤10^9</p>
<h3 id="输出描述-2"><a href="#输出描述-2" class="headerlink" title="输出描述"></a>输出描述</h3><p>输出共 1 行，包含 NN个整数，表示每个彩灯的亮度。</p>
<h3 id="输入输出样例-2"><a href="#输入输出样例-2" class="headerlink" title="输入输出样例"></a>输入输出样例</h3><h4 id="示例-1-1"><a href="#示例-1-1" class="headerlink" title="示例 1"></a>示例 1</h4><blockquote>
<p>输入</p>
</blockquote>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">5 3</span><br><span class="line">2 2 2 1 5</span><br><span class="line">1 3 3</span><br><span class="line">4 5 5</span><br><span class="line">1 1 -100</span><br></pre></td></tr></table></figure>

<blockquote>
<p>输出</p>
</blockquote>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">0 5 5 6 10</span><br></pre></td></tr></table></figure>

<h3 id="运行限制-4"><a href="#运行限制-4" class="headerlink" title="运行限制"></a>运行限制</h3><ul>
<li>最大运行时间：1s</li>
<li>最大运行内存: 128M</li>
</ul>
<h3 id="题解-4"><a href="#题解-4" class="headerlink" title="题解"></a>题解</h3><p>用到了差分。</p>
<p><strong>一维差分结论</strong>：给<code>a</code>数组中的<code>[l, r] </code>区间中的每一个数都加上<code>c</code>,只需对差分数组<code>b</code>做 <code>b[l] += c</code>, <code>b[r+1] -= c </code>。时间复杂度为<code>O(1)</code>, 大大提高了效率。 </p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="type">long</span> <span class="type">long</span> light[<span class="number">500005</span>],f[<span class="number">500005</span>];</span><br><span class="line"><span class="comment">//light-灯数组，f-差分数组</span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">  <span class="comment">// 请在此输入您的代码</span></span><br><span class="line">  <span class="type">long</span> <span class="type">long</span> n,q,l,r,x;</span><br><span class="line">  </span><br><span class="line">  cin &gt;&gt; n &gt;&gt; q;</span><br><span class="line">  <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>;i &lt;= n;i++) &#123;</span><br><span class="line">    cin &gt;&gt; light[i];</span><br><span class="line">    f[i] = light[i]-light[i<span class="number">-1</span>];  <span class="comment">//计算差分数组 </span></span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">while</span>(q--) &#123;</span><br><span class="line">    cin &gt;&gt; l &gt;&gt; r &gt;&gt; x;</span><br><span class="line">    f[l] += x;</span><br><span class="line">    f[r+<span class="number">1</span>] -= x;</span><br><span class="line">  &#125;</span><br><span class="line">  </span><br><span class="line">  <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>;i &lt;= n;i++) &#123;</span><br><span class="line">    f[i] += f[i<span class="number">-1</span>];  <span class="comment">//求差分数组前缀</span></span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>;i &lt;= n;i++) &#123;</span><br><span class="line">    <span class="keyword">if</span>(f[i] &lt; <span class="number">0</span>) &#123;</span><br><span class="line">      f[i] = <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    cout &lt;&lt; f[i] &lt;&lt; <span class="string">&quot; &quot;</span>;</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="小明的背包1-dp"><a href="#小明的背包1-dp" class="headerlink" title="小明的背包1(dp)"></a>小明的背包1(dp)</h2><h3 id="题目描述-5"><a href="#题目描述-5" class="headerlink" title="题目描述"></a>题目描述</h3><p><a target="_blank" rel="noopener" href="https://www.lanqiao.cn/problems/1174/learning/">小明的背包1 - 蓝桥云课 (lanqiao.cn)</a> </p>
<p>小明有一个容量为 V 的背包。</p>
<p>这天他去商场购物，商场一共有 N 件物品，第 i 件物品的体积为 wi，价值为 vi。</p>
<p>小明想知道在购买的物品总体积不超过 V 的情况下所能获得的最大价值为多少，请你帮他算算。</p>
<h3 id="输入描述-3"><a href="#输入描述-3" class="headerlink" title="输入描述"></a>输入描述</h3><p>输入第 11行包含两个正整数 N,V，表示商场物品的数量和小明的背包容量。</p>
<p>第 2∼N+1 行包含 22个正整数 w,v，表示物品的体积和价值。</p>
<p>1≤N≤10^2，1≤V≤10^3，1≤wi,vi≤10^3。</p>
<h3 id="输出描述-3"><a href="#输出描述-3" class="headerlink" title="输出描述"></a>输出描述</h3><p>输出一行整数表示小明所能获得的最大价值。</p>
<h3 id="输入输出样例-3"><a href="#输入输出样例-3" class="headerlink" title="输入输出样例"></a>输入输出样例</h3><h4 id="示例-1-2"><a href="#示例-1-2" class="headerlink" title="示例 1"></a>示例 1</h4><blockquote>
<p>输入</p>
</blockquote>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">5 20</span><br><span class="line">1 6</span><br><span class="line">2 5</span><br><span class="line">3 8</span><br><span class="line">5 15</span><br><span class="line">3 3 </span><br></pre></td></tr></table></figure>

<blockquote>
<p>输出</p>
</blockquote>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">37</span><br></pre></td></tr></table></figure>

<h3 id="运行限制-5"><a href="#运行限制-5" class="headerlink" title="运行限制"></a>运行限制</h3><ul>
<li>最大运行时间：1s</li>
<li>最大运行内存: 128M</li>
</ul>
<h3 id="题解-5"><a href="#题解-5" class="headerlink" title="题解"></a>题解</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="type">int</span> w[<span class="number">105</span>],v[<span class="number">105</span>];</span><br><span class="line"><span class="type">int</span> dp[<span class="number">105</span>][<span class="number">1005</span>];  <span class="comment">//dp[i][j]:i件物品体积一共为j时的价值</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">  <span class="type">int</span> N,V;</span><br><span class="line"></span><br><span class="line">  cin &gt;&gt; N &gt;&gt; V;</span><br><span class="line">  <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>;i &lt; N;i++) &#123;</span><br><span class="line">    cin &gt;&gt; w[i] &gt;&gt; v[i];</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">1</span>;j &lt;= V;j++) &#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>;i &lt;= N;i++) &#123;</span><br><span class="line">      <span class="keyword">if</span>(j &gt;= w[i<span class="number">-1</span>]) &#123;</span><br><span class="line">        dp[i][j] = <span class="built_in">max</span>(dp[i<span class="number">-1</span>][j],dp[i<span class="number">-1</span>][j-w[i<span class="number">-1</span>]]+v[i<span class="number">-1</span>]);</span><br><span class="line">      &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">        dp[i][j] = dp[i<span class="number">-1</span>][j];</span><br><span class="line">      &#125;</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  cout &lt;&lt; dp[N][V];</span><br><span class="line"></span><br><span class="line">  <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="走迷宫-BFS"><a href="#走迷宫-BFS" class="headerlink" title="走迷宫(BFS)"></a>走迷宫(BFS)</h2><h3 id="题目描述-6"><a href="#题目描述-6" class="headerlink" title="题目描述"></a>题目描述</h3><p><a target="_blank" rel="noopener" href="https://www.lanqiao.cn/problems/1216/learning/">走迷宫 - 蓝桥云课 (lanqiao.cn)</a> </p>
<p>给定一个 N×M 的网格迷宫 G。G 的每个格子要么是道路，要么是障碍物（道路用 1 表示，障碍物用 0 表示）。</p>
<p>已知迷宫的入口位置为(x1,y1)，出口位置为 (x2,y2)。问从入口走到出口，最少要走多少个格子。</p>
<h3 id="输入描述-4"><a href="#输入描述-4" class="headerlink" title="输入描述"></a>输入描述</h3><p>输入第 1 行包含两个正整数 N,M，分别表示迷宫的大小。</p>
<p>接下来输入一个 N×M 的矩阵。若Gi,j&#x3D;1 表示其为道路，否则表示其为障碍物。</p>
<p>最后一行输入四个整数 x1,y1,x2,y2，表示入口的位置和出口的位置。</p>
<p>1≤N,M≤10^2，0≤Gi,j≤1，1≤x1,x2≤N，1≤y1,y2≤M。</p>
<h3 id="输出描述-4"><a href="#输出描述-4" class="headerlink" title="输出描述"></a>输出描述</h3><p>输出仅一行，包含一个整数表示答案。</p>
<p>若无法从入口到出口，则输出 −1。</p>
<h3 id="输入输出样例-4"><a href="#输入输出样例-4" class="headerlink" title="输入输出样例"></a>输入输出样例</h3><h4 id="示例-1-3"><a href="#示例-1-3" class="headerlink" title="示例 1"></a>示例 1</h4><blockquote>
<p>输入</p>
</blockquote>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">5 5 </span><br><span class="line">1 0 1 1 0</span><br><span class="line">1 1 0 1 1 </span><br><span class="line">0 1 0 1 1</span><br><span class="line">1 1 1 1 1</span><br><span class="line">1 0 0 0 1</span><br><span class="line">1 1 5 5 </span><br></pre></td></tr></table></figure>

<blockquote>
<p>输出</p>
</blockquote>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">8</span><br></pre></td></tr></table></figure>

<h3 id="运行限制-6"><a href="#运行限制-6" class="headerlink" title="运行限制"></a>运行限制</h3><ul>
<li>最大运行时间：1s</li>
<li>最大运行内存: 128M</li>
</ul>
<h3 id="题解-6"><a href="#题解-6" class="headerlink" title="题解"></a>题解</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> n,m;</span><br><span class="line"><span class="type">int</span> x1,y1,x2,y2;</span><br><span class="line"><span class="type">int</span> grid[<span class="number">105</span>][<span class="number">105</span>],vis[<span class="number">105</span>][<span class="number">105</span>];</span><br><span class="line"><span class="type">int</span> dx[] = &#123;<span class="number">0</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">-1</span>&#125;;</span><br><span class="line"><span class="type">int</span> dy[] = &#123;<span class="number">1</span>,<span class="number">-1</span>,<span class="number">0</span>,<span class="number">0</span>&#125;;</span><br><span class="line"></span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">point</span>&#123;</span><br><span class="line">    <span class="type">int</span> x;</span><br><span class="line">    <span class="type">int</span> y;</span><br><span class="line">    <span class="type">int</span> step;</span><br><span class="line">&#125;;</span><br><span class="line">queue&lt;point&gt; q;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    point start,temp;</span><br><span class="line">    <span class="type">int</span> flag = <span class="number">0</span>,posX,posY;</span><br><span class="line"></span><br><span class="line">    cin &gt;&gt; n &gt;&gt; m;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>;i &lt;= n;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">1</span>;j &lt;= m;j++) &#123;</span><br><span class="line">            cin &gt;&gt; grid[i][j];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    cin &gt;&gt; x1 &gt;&gt; y1 &gt;&gt; x2 &gt;&gt; y2;</span><br><span class="line"></span><br><span class="line">    start.x = x1;</span><br><span class="line">    start.y = y1;</span><br><span class="line">    start.step = <span class="number">0</span>;</span><br><span class="line">    vis[x1][y1] = <span class="number">1</span>;</span><br><span class="line">    </span><br><span class="line">    q.<span class="built_in">push</span>(start);</span><br><span class="line">    <span class="keyword">while</span>(!q.<span class="built_in">empty</span>()) &#123;</span><br><span class="line">        <span class="keyword">if</span>(q.<span class="built_in">front</span>().x == x2 &amp;&amp; q.<span class="built_in">front</span>().y == y2) &#123;</span><br><span class="line">            flag = <span class="number">1</span>;  <span class="comment">//能够走到终点</span></span><br><span class="line">            cout &lt;&lt; q.<span class="built_in">front</span>().step;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>;i &lt; <span class="number">4</span>;i++) &#123;</span><br><span class="line">            posX = q.<span class="built_in">front</span>().x + dx[i];</span><br><span class="line">            posY = q.<span class="built_in">front</span>().y + dy[i];</span><br><span class="line">            <span class="keyword">if</span>(grid[posX][posY] == <span class="number">1</span> &amp;&amp; vis[posX][posY] == <span class="number">0</span>) &#123;</span><br><span class="line">                temp.x = posX;</span><br><span class="line">                temp.y = posY;</span><br><span class="line">                temp.step = q.<span class="built_in">front</span>().step + <span class="number">1</span>;</span><br><span class="line">                q.<span class="built_in">push</span>(temp);</span><br><span class="line">                vis[posX][posY] = <span class="number">1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        q.<span class="built_in">pop</span>();</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">if</span>(flag == <span class="number">0</span>) &#123;</span><br><span class="line">        cout &lt;&lt; <span class="string">&quot;-1&quot;</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="蓝桥骑士-中等"><a href="#蓝桥骑士-中等" class="headerlink" title="蓝桥骑士(中等)"></a>蓝桥骑士(中等)</h2><h3 id="题目描述-7"><a href="#题目描述-7" class="headerlink" title="题目描述"></a>题目描述</h3><p><a target="_blank" rel="noopener" href="https://www.lanqiao.cn/problems/1188/learning/">蓝桥骑士 - 蓝桥云课 (lanqiao.cn)</a> </p>
<p>小明是蓝桥王国的骑士，他喜欢不断突破自我。</p>
<p>这天蓝桥国王给他安排了 N 个对手，他们的战力值分别为 a1,a2,…,an，且按顺序阻挡在小明的前方。对于这些对手小明可以选择挑战，也可以选择避战。</p>
<p>身为高傲的骑士，小明从不走回头路，且只愿意挑战战力值越来越高的对手。</p>
<p>请你算算小明最多会挑战多少名对手。</p>
<h3 id="输入描述-5"><a href="#输入描述-5" class="headerlink" title="输入描述"></a>输入描述</h3><p>输入第一行包含一个整数 N，表示对手的个数。</p>
<p>第二行包含 N 个整数 a1,a2,…,an，分别表示对手的战力值。</p>
<p>1≤N≤3×10^5，1≤ai≤10^9。</p>
<h3 id="输出描述-5"><a href="#输出描述-5" class="headerlink" title="输出描述"></a>输出描述</h3><p>输出一行整数表示答案。</p>
<h3 id="输入输出样例-5"><a href="#输入输出样例-5" class="headerlink" title="输入输出样例"></a>输入输出样例</h3><h4 id="示例-1-4"><a href="#示例-1-4" class="headerlink" title="示例 1"></a>示例 1</h4><blockquote>
<p>输入</p>
</blockquote>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">6</span><br><span class="line">1 4 2 2 5 6</span><br></pre></td></tr></table></figure>

<blockquote>
<p>输出</p>
</blockquote>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">4</span><br></pre></td></tr></table></figure>

<h3 id="运行限制-7"><a href="#运行限制-7" class="headerlink" title="运行限制"></a>运行限制</h3><ul>
<li>最大运行时间：1s</li>
<li>最大运行内存: 128M</li>
</ul>
<h3 id="题解-7"><a href="#题解-7" class="headerlink" title="题解"></a>题解</h3><blockquote>
<p>我们举一个例子：有以下序列A[ ] &#x3D; 3 1 2 6 4 5 10 7，求LIS长度。</p>
<p>我们定义一个B[ i ]来储存可能的排序序列，len 为LIS长度。我们依次把A[ i ]有序地放进B[ i ]里。</p>
<p>（为了方便，i的范围就从1~n表示第i个数）</p>
<p>A[1] &#x3D; 3，把3放进B[1]，此时B[1] &#x3D; 3，此时len &#x3D; 1，最小末尾是3</p>
<p>A[2] &#x3D; 1，因为1比3小，所以可以把B[1]中的3替换为1，此时B[1] &#x3D; 1，此时len &#x3D; 1，最小末尾是1</p>
<p>A[3] &#x3D; 2，2大于1，就把2放进B[2] &#x3D; 2，此时B[ ]&#x3D;{1,2}，len &#x3D; 2</p>
<p>同理，A[4]&#x3D;6，把6放进B[3] &#x3D; 6，B[ ]&#x3D;{1,2,6}，len &#x3D; 3</p>
<p>A[5]&#x3D;4，4在2和6之间，比6小，可以把B[3]替换为4，B[ ] &#x3D; {1,2,4}，len &#x3D; 3</p>
<p>A[6] &#x3D; 5，B[4] &#x3D; 5，B[ ] &#x3D; {1,2,4,5}，len &#x3D; 4 </p>
<p>A[7] &#x3D; 10，B[5] &#x3D; 10，B[ ] &#x3D; {1,2,4,5,10}，len &#x3D; 5</p>
<p>A[8] &#x3D; 7，7在5和10之间，比10小，可以把B[5]替换为7，B[ ] &#x3D; {1,2,4,5,7}，len &#x3D; 5</p>
<p>最终我们得出LIS长度为5，但是，但是！！！B[ ] 中的<strong>序列并不一定是正确的最长上升子序列。</strong></p>
</blockquote>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> num[<span class="number">300005</span>],low[<span class="number">300005</span>];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">change</span><span class="params">(<span class="type">int</span> l,<span class="type">int</span> r,<span class="type">int</span> val)</span> </span>&#123;</span><br><span class="line">  <span class="comment">//二分法找到low数组中第一个比val大的数，替换</span></span><br><span class="line">  <span class="type">int</span> mid;</span><br><span class="line">  <span class="keyword">while</span>(l &lt;= r) &#123;</span><br><span class="line">    mid = (l+r)/<span class="number">2</span>;</span><br><span class="line">    <span class="keyword">if</span>(low[mid] &lt;= val) &#123;</span><br><span class="line">      l = mid+<span class="number">1</span>;</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">      r = mid<span class="number">-1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line">  low[l] = val;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">  <span class="type">int</span> n,ans = <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">  cin &gt;&gt; n;</span><br><span class="line">  <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; n; ++i) &#123;</span><br><span class="line">    cin &gt;&gt; num[i];</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  low[ans] = num[<span class="number">0</span>];</span><br><span class="line">  <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt; n; ++i) &#123;</span><br><span class="line">    <span class="keyword">if</span>(num[i] &gt; low[ans]) &#123;</span><br><span class="line">      ans++;</span><br><span class="line">      low[ans] = num[i];</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">      <span class="built_in">change</span>(<span class="number">0</span>,ans,num[i]);</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  cout &lt;&lt; ans;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="蓝桥侦探-中等"><a href="#蓝桥侦探-中等" class="headerlink" title="蓝桥侦探(中等)"></a>蓝桥侦探(中等)</h2><h3 id="题目描述-8"><a href="#题目描述-8" class="headerlink" title="题目描述"></a>题目描述</h3><p><a target="_blank" rel="noopener" href="https://www.lanqiao.cn/problems/1136/learning/">蓝桥侦探 - 蓝桥云课 (lanqiao.cn)</a> </p>
<p>小明是蓝桥王国的侦探。</p>
<p>这天，他接收到一个任务，任务的名字叫分辨是非，具体如下：</p>
<p>蓝桥皇宫的国宝被人偷了，犯罪嫌疑人锁定在 N 个大臣之中，他们的编号分别为1∼N。</p>
<p>在案发时这 N 个大臣要么在大厅1，要么在大厅2，但具体在哪个大厅他们也不记得了。</p>
<p>审讯完他们之后，小明把他们的提供的信息按顺序记了下来，一共 M 条，形式如下：</p>
<ul>
<li><code>x y</code>，表示大臣 x 提供的信息，信息内容为：案发时他和大臣 y 不在一个大厅。</li>
</ul>
<p>小明喜欢按顺序读信息，他会根据信息内容尽可能对案发时大臣的位置进行编排。</p>
<p>他推理得出第一个与先前信息产生矛盾的信息提出者就是偷窃者，但推理的过程已经耗费了他全部的脑力，他筋疲力尽的睡了过去。作为他的侦探助手，请你帮助他找出偷窃者！</p>
<h3 id="输入描述-6"><a href="#输入描述-6" class="headerlink" title="输入描述"></a>输入描述</h3><p>第 1 行包含两个正整数 N,M，分别表示大臣的数量和口供的数量。</p>
<p>之后的第 2∼M+1 行每行输入两个整数 x,y，表示口供的信息。</p>
<p>1≤N,M≤5×10^5，1≤x,y≤N。</p>
<h3 id="输出描述-6"><a href="#输出描述-6" class="headerlink" title="输出描述"></a>输出描述</h3><p>输出仅一行，包含一个正整数，表示偷窃者的编号。</p>
<h3 id="输入输出样例-6"><a href="#输入输出样例-6" class="headerlink" title="输入输出样例"></a>输入输出样例</h3><h4 id="示例-1-5"><a href="#示例-1-5" class="headerlink" title="示例 1"></a>示例 1</h4><blockquote>
<p>输入</p>
</blockquote>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">4 5 </span><br><span class="line">1 2</span><br><span class="line">1 3 </span><br><span class="line">2 3 </span><br><span class="line">3 4</span><br><span class="line">1 4</span><br></pre></td></tr></table></figure>

<blockquote>
<p>输出</p>
</blockquote>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">2</span><br></pre></td></tr></table></figure>

<h3 id="运行限制-8"><a href="#运行限制-8" class="headerlink" title="运行限制"></a>运行限制</h3><ul>
<li>最大运行时间：1s</li>
<li>最大运行内存: 256M</li>
</ul>
<h3 id="题解-8"><a href="#题解-8" class="headerlink" title="题解"></a>题解</h3><p>普通的并查集只能维护“朋友的朋友是朋友”的关系，种类并查集可以维护“敌人的敌人是朋友”，也叫做并查集的扩展域。主要为：对于一个个体a，假设存在与a对立的个体a+n，如果b与a对立，那么b与a+n在同一并查集（朋友），a与b+n也在同一并查集；反之如果b与a是朋友，那么b与a+n不在同一并查集（对立），即a与b在同一并查集，a+n与b+n在同一并查集。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> pre[<span class="number">1000005</span>];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">find</span><span class="params">(<span class="type">int</span> x)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(pre[x] == x) &#123;</span><br><span class="line">      <span class="keyword">return</span> x;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> pre[x] = <span class="built_in">find</span>(pre[x]);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">join</span><span class="params">(<span class="type">int</span> x,<span class="type">int</span> y)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> fx=<span class="built_in">find</span>(x), fy=<span class="built_in">find</span>(y);</span><br><span class="line">    <span class="keyword">if</span>(fx != fy) &#123;</span><br><span class="line">        pre[fx]=fy;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">  <span class="type">int</span> n,m,x,y;</span><br><span class="line">  <span class="type">int</span> ans = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">  cin &gt;&gt; n &gt;&gt; m;</span><br><span class="line">  <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>;i &lt;= <span class="number">2</span>*n;i++) &#123;</span><br><span class="line">    pre[i] = i;</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>;i &lt; m;++i) &#123;</span><br><span class="line">    cin &gt;&gt; x &gt;&gt; y;</span><br><span class="line">    <span class="keyword">if</span>(ans == <span class="number">0</span>) &#123;</span><br><span class="line">      <span class="keyword">if</span>(<span class="built_in">find</span>(x) == <span class="built_in">find</span>(y) || <span class="built_in">find</span>(x+n) == <span class="built_in">find</span>(y+n)) &#123;</span><br><span class="line">        ans = x;</span><br><span class="line">        <span class="keyword">continue</span>;</span><br><span class="line">      &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">        <span class="built_in">join</span>(x+n,y);</span><br><span class="line">        <span class="built_in">join</span>(x,y+n);</span><br><span class="line">      &#125;</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">      <span class="keyword">break</span>;</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  cout &lt;&lt; ans;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="锻造兵器"><a href="#锻造兵器" class="headerlink" title="锻造兵器"></a>锻造兵器</h2><h3 id="题目描述-9"><a href="#题目描述-9" class="headerlink" title="题目描述"></a>题目描述</h3><p><a target="_blank" rel="noopener" href="https://www.lanqiao.cn/problems/1374/learning/">锻造兵器 - 蓝桥云课 (lanqiao.cn)</a> </p>
<p>小明一共有 n块锻造石，第 i 块锻造石的属性值为 ai。</p>
<p>现在小明决定从这 n 块锻造石中任取两块来锻造兵器。</p>
<p>通过周密计算，小明得出，只有当两块锻造石的属性值的差值等于 C，兵器才能锻造成功。</p>
<p>请你帮小明算算，他有多少种选取锻造石的方案可以使得锻造成功。</p>
<h3 id="输入描述-7"><a href="#输入描述-7" class="headerlink" title="输入描述"></a>输入描述</h3><p>第一行包含两个整数 n,C，其含义如题所述。</p>
<p>接下来一行包含 n 个整数，分别表示 a1,a2,⋯,an。</p>
<p>1≤N≤2×10^5，∣ai∣≤10^4 , 0≤C≤10^9。</p>
<h3 id="输出描述-7"><a href="#输出描述-7" class="headerlink" title="输出描述"></a>输出描述</h3><p>输出共一行，包含一个整数，表示答案。</p>
<h3 id="输入输出样例-7"><a href="#输入输出样例-7" class="headerlink" title="输入输出样例"></a>输入输出样例</h3><h4 id="示例-1-6"><a href="#示例-1-6" class="headerlink" title="示例 1"></a>示例 1</h4><blockquote>
<p>输入</p>
</blockquote>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">6 3</span><br><span class="line">8 4 5 7 7 4</span><br></pre></td></tr></table></figure>

<blockquote>
<p>输出</p>
</blockquote>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">5</span><br></pre></td></tr></table></figure>

<h3 id="运行限制-9"><a href="#运行限制-9" class="headerlink" title="运行限制"></a>运行限制</h3><ul>
<li>最大运行时间：1s</li>
<li>最大运行内存: 128M</li>
</ul>
<h3 id="题解-9"><a href="#题解-9" class="headerlink" title="题解"></a>题解</h3><p>这题如果用暴力法统计数对，很显然，复杂度为 O(n^2)，超时。所以下面试试尺取法。</p>
<p>首先第一步肯定是排序，那么对输入样例排序后得 {4 4 5 7 7 8}，其中第一个 4 和后面两个 7 是两对，第二个 4 和后面两个 7 也是两对，共四对。这用尺取法该如何实现？</p>
<p>如果仅使用 i、j 两个指针，确实是无法实现的，但如果把后面两个 7看成一个整体，一起统计数对，是不是就可以了？我们可以用两个指针 j、k 指示这种区间，[j, k] 区间内每个数都相同，这个区间可以产生 k – j个数对。使用三个指针，i 是主指针，从头到尾遍历 n 个数；j、k 是辅助指针，用于查找数字相同的区间 [j, k]。</p>
<p>代码只有一个 for 循环，且 j和 k 随着 i 递增，所以总复杂度为 O(n)。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;map&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> a[<span class="number">200005</span>];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">  <span class="type">int</span> n,c;</span><br><span class="line">  <span class="type">long</span> <span class="type">long</span> cnt = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">  cin &gt;&gt; n &gt;&gt; c;</span><br><span class="line">  <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>;i &lt;= n;i++) &#123;</span><br><span class="line">    cin &gt;&gt; a[i];</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  <span class="built_in">sort</span>(a+<span class="number">1</span>,a+n+<span class="number">1</span>);</span><br><span class="line"></span><br><span class="line">  <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>,j = <span class="number">1</span>,k = <span class="number">1</span>;i &lt;= n;i++) &#123;</span><br><span class="line">    <span class="keyword">while</span>(j &lt;= n &amp;&amp; a[j] &lt; a[i]+c) &#123;</span><br><span class="line">      j++;  <span class="comment">//用j、k查找数字相同的区间</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(k &lt;= n &amp;&amp; a[k] &lt;= a[i]+c) &#123;</span><br><span class="line">      k++;  <span class="comment">//区间[j,k]内所有数字相同</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(a[j]-a[i] == c) &#123;</span><br><span class="line">      cnt += (k-j);</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  cout &lt;&lt; cnt;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="最长公共子序列"><a href="#最长公共子序列" class="headerlink" title="最长公共子序列"></a>最长公共子序列</h2><h3 id="题目描述-10"><a href="#题目描述-10" class="headerlink" title="题目描述"></a>题目描述</h3><p>给定一个长度为 N 数组 a 和一个长度为 M 的数组 b。</p>
<p>请你求出它们的最长公共子序列长度为多少。</p>
<h3 id="输入描述-8"><a href="#输入描述-8" class="headerlink" title="输入描述"></a>输入描述</h3><p>输入第一行包含两个整数 N,M，分别表示数组 a 和 b 的长度。</p>
<p>第二行包含 N 个整数 a1,a2,…,an。</p>
<p>第三行包含 M 个整数 b1,b2,…,bn。</p>
<p>1≤N,M≤10^3，1≤ai,bi≤10^9。</p>
<h3 id="输出描述-8"><a href="#输出描述-8" class="headerlink" title="输出描述"></a>输出描述</h3><p>输出一行整数表示答案。</p>
<h3 id="输入输出样例-8"><a href="#输入输出样例-8" class="headerlink" title="输入输出样例"></a>输入输出样例</h3><h4 id="示例-1-7"><a href="#示例-1-7" class="headerlink" title="示例 1"></a>示例 1</h4><blockquote>
<p>输入</p>
</blockquote>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">5 6</span><br><span class="line">1 2 3 4 5</span><br><span class="line">2 3 2 1 4 5</span><br></pre></td></tr></table></figure>

<blockquote>
<p>输出</p>
</blockquote>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">4</span><br></pre></td></tr></table></figure>

<h3 id="运行限制-10"><a href="#运行限制-10" class="headerlink" title="运行限制"></a>运行限制</h3><ul>
<li>最大运行时间：1s</li>
<li>最大运行内存: 128M</li>
</ul>
<h3 id="题解-10"><a href="#题解-10" class="headerlink" title="题解"></a>题解</h3><table>
<thead>
<tr>
<th>dp</th>
<th></th>
<th>2</th>
<th>3</th>
<th>2</th>
<th>1</th>
<th>4</th>
<th>5</th>
</tr>
</thead>
<tbody><tr>
<td></td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
</tr>
<tr>
<td>1</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>1</td>
<td>1</td>
<td>1</td>
</tr>
<tr>
<td>2</td>
<td>0</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
</tr>
<tr>
<td>3</td>
<td>0</td>
<td>1</td>
<td>2</td>
<td>2</td>
<td>2</td>
<td>2</td>
<td>2</td>
</tr>
<tr>
<td>4</td>
<td>0</td>
<td>1</td>
<td>2</td>
<td>2</td>
<td>2</td>
<td>3</td>
<td>3</td>
</tr>
<tr>
<td>5</td>
<td>0</td>
<td>1</td>
<td>2</td>
<td>2</td>
<td>2</td>
<td>3</td>
<td>4</td>
</tr>
</tbody></table>
<p>表格中dp[i][j]位置的数值含义是，当取1-i个第一个字符串(a)的字母和取1-j个第二个字符串的字母(b)，最长公共子序列的长度是dp[i][j]。具体填表的过程可以以如下状态转移方程来表示： </p>
<p>有两种情况</p>
<p>1:当a[i]&#x3D;&#x3D;b[j]时，则当前状态转移方程为dp[i][j]&#x3D;d[i-1][j-1]+1;</p>
<p>2:当不相等时，则从dp[i-1][j]和dp[i][j-1]中取最大值赋值当前的dp[i][j]，状态转移方程为</p>
<p>dp[i][j]&#x3D;max(dp[i-1][j],dp[i][j-1]）。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="type">int</span> a[<span class="number">1005</span>],b[<span class="number">1005</span>],dp[<span class="number">1005</span>][<span class="number">1005</span>];</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">  <span class="type">int</span> n,m;</span><br><span class="line">  cin &gt;&gt; n &gt;&gt; m;</span><br><span class="line">  <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>;i &lt;= n;i++) &#123;</span><br><span class="line">    cin &gt;&gt; a[i];</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>;i &lt;= m;i++) &#123;</span><br><span class="line">    cin &gt;&gt; b[i];</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>;i &lt;= n;i++) &#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">1</span>;j &lt;= m;j++) &#123;</span><br><span class="line">      <span class="keyword">if</span>(a[i] == b[j]) &#123;</span><br><span class="line">        dp[i][j] = dp[i<span class="number">-1</span>][j<span class="number">-1</span>]+<span class="number">1</span>;</span><br><span class="line">      &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">        dp[i][j] = <span class="built_in">max</span>(dp[i<span class="number">-1</span>][j],dp[i][j<span class="number">-1</span>]);</span><br><span class="line">      &#125;</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">  cout &lt;&lt; dp[n][m];</span><br><span class="line"></span><br><span class="line">  <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="小明的衣服"><a href="#小明的衣服" class="headerlink" title="小明的衣服"></a>小明的衣服</h2><h3 id="题目描述-11"><a href="#题目描述-11" class="headerlink" title="题目描述"></a>题目描述</h3><p>小明买了 n 件白色的衣服，他觉得所有衣服都是一种颜色太单调，希望对这些衣服进行染色，每次染色时，他会将某种颜色的<strong>所有</strong>衣服寄去染色厂，第 i 件衣服的邮费为 ai 元，染色厂会按照小明的要求将其中一部分衣服染成同一种任意的颜色，之后将衣服寄给小明， 请问小明要将 n 件衣服染成不同颜色的最小代价是多少？</p>
<h3 id="输入描述-9"><a href="#输入描述-9" class="headerlink" title="输入描述"></a>输入描述</h3><p>第一行为一个整数 n ，表示衣服的数量。</p>
<p>第二行包括n 个整数 a1,a2…an 表示第 i 件衣服的邮费为ai 元。</p>
<p>（1≤n≤105,1≤ai≤109 ）</p>
<h3 id="输出描述-9"><a href="#输出描述-9" class="headerlink" title="输出描述"></a>输出描述</h3><p>输出一个整数表示小明所要花费的最小代价。</p>
<h3 id="输入输出样例-9"><a href="#输入输出样例-9" class="headerlink" title="输入输出样例"></a>输入输出样例</h3><h4 id="示例-1-8"><a href="#示例-1-8" class="headerlink" title="示例 1"></a>示例 1</h4><blockquote>
<p>输入</p>
</blockquote>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">5</span><br><span class="line">5 1 3 2 1 </span><br></pre></td></tr></table></figure>

<blockquote>
<p>输出</p>
</blockquote>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">25</span><br></pre></td></tr></table></figure>

<h3 id="运行限制-11"><a href="#运行限制-11" class="headerlink" title="运行限制"></a>运行限制</h3><ul>
<li>最大运行时间：1s</li>
<li>最大运行内存: 256M</li>
</ul>
<h3 id="题解-11"><a href="#题解-11" class="headerlink" title="题解"></a>题解</h3><p>题目释义：</p>
<ol>
<li>染色时 需要把所有同色的衣服寄到厂家，然后进行染色策略厂家寄回，花费代价为小明寄到染色厂的邮费（厂家包邮 doge.jpg）</li>
<li>初始所有衣服都为白色 &#x3D;&#x3D;&gt; 第一次需要把所有衣服寄到厂家</li>
<li>染色策略为选择一部分衣服染成同一颜色，再把所有的衣服寄回</li>
<li>要求把 <strong>n</strong> 件衣服染成不同颜色的代价</li>
</ol>
<p>综上，因为染色策略是染成同一颜色，寄出策略也是同一颜色，想要得到不同颜色的结果就需要在每次染色时出一个不同颜色。 可以每次选一个染成不同的颜色，也可以选 <strong>i-1</strong> 个染成不同颜色，两种染色方式导致的结果相同。</p>
<p>所以为了获取最小代价，可以每次贪心的选择邮寄代价最大的衣服染出不同的颜色，可以防止邮寄代价较大的衣服重复寄出。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line">priority_queue&lt;<span class="type">long</span> <span class="type">long</span>,vector&lt;<span class="type">long</span> <span class="type">long</span>&gt;,greater&lt;<span class="type">long</span> <span class="type">long</span>&gt;&gt; q;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">long</span> <span class="type">long</span> n = <span class="number">0</span>,temp = <span class="number">0</span>,a = <span class="number">0</span>,b = <span class="number">0</span>,sum = <span class="number">0</span>,ans = <span class="number">0</span>;</span><br><span class="line">    cin &gt;&gt; n;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>;i &lt; n;i++) &#123;</span><br><span class="line">      cin &gt;&gt; temp;</span><br><span class="line">      q.<span class="built_in">push</span>(temp);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">while</span>(q.<span class="built_in">size</span>() &gt; <span class="number">1</span>) &#123;</span><br><span class="line">      a = q.<span class="built_in">top</span>();</span><br><span class="line">      q.<span class="built_in">pop</span>();</span><br><span class="line">      b = q.<span class="built_in">top</span>();</span><br><span class="line">      q.<span class="built_in">pop</span>();</span><br><span class="line">      sum = a+b;</span><br><span class="line">      ans += sum;</span><br><span class="line">      q.<span class="built_in">push</span>(sum);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    cout &lt;&lt; ans;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>


    </div>

    
    
    

      <footer class="post-footer">
          <div class="post-tags">
              <a href="/xlrblog/tags/Note/" rel="tag"># Note</a>
              <a href="/xlrblog/tags/Practices/" rel="tag"># Practices</a>
          </div>

        


        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/xlrblog/2023/01/06/JDBC%E5%AD%A6%E4%B9%A0/" rel="prev" title="JDBC学习">
      <i class="fa fa-chevron-left"></i> JDBC学习
    </a></div>
      <div class="post-nav-item">
    <a href="/xlrblog/2023/01/07/Maven%E5%9F%BA%E7%A1%80/" rel="next" title="Maven基础">
      Maven基础 <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  



          </div>
          

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%95%B0%E5%AD%97%E4%B8%89%E8%A7%92%E5%BD%A2-%E7%AE%80%E5%8D%95"><span class="nav-number">1.</span> <span class="nav-text">数字三角形(简单)</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-number">1.1.</span> <span class="nav-text">题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0"><span class="nav-number">1.2.</span> <span class="nav-text">输入描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0"><span class="nav-number">1.3.</span> <span class="nav-text">输出描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%85%A5%E8%BE%93%E5%87%BA%E6%A0%B7%E4%BE%8B"><span class="nav-number">1.4.</span> <span class="nav-text">输入输出样例</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E7%A4%BA%E4%BE%8B"><span class="nav-number">1.4.1.</span> <span class="nav-text">示例</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BF%90%E8%A1%8C%E9%99%90%E5%88%B6"><span class="nav-number">1.5.</span> <span class="nav-text">运行限制</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E8%A7%A3"><span class="nav-number">1.6.</span> <span class="nav-text">题解</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%8E%92%E5%BA%8F-%E7%AE%80%E5%8D%95%EF%BC%89"><span class="nav-number">2.</span> <span class="nav-text">排序(简单）</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0-1"><span class="nav-number">2.1.</span> <span class="nav-text">题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BF%90%E8%A1%8C%E9%99%90%E5%88%B6-1"><span class="nav-number">2.2.</span> <span class="nav-text">运行限制</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E8%A7%A3-1"><span class="nav-number">2.3.</span> <span class="nav-text">题解</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%9D%A8%E8%BE%89%E4%B8%89%E8%A7%92%E5%BD%A2-%E4%B8%AD%E7%AD%89"><span class="nav-number">3.</span> <span class="nav-text">杨辉三角形(中等)</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0-2"><span class="nav-number">3.1.</span> <span class="nav-text">题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0-1"><span class="nav-number">3.2.</span> <span class="nav-text">输入描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0-1"><span class="nav-number">3.3.</span> <span class="nav-text">输出描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%85%A5%E8%BE%93%E5%87%BA%E6%A0%B7%E4%BE%8B-1"><span class="nav-number">3.4.</span> <span class="nav-text">输入输出样例</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E7%A4%BA%E4%BE%8B-1"><span class="nav-number">3.4.1.</span> <span class="nav-text">示例 1</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%AF%84%E6%B5%8B%E7%94%A8%E4%BE%8B%E8%A7%84%E6%A8%A1%E4%B8%8E%E7%BA%A6%E5%AE%9A"><span class="nav-number">3.5.</span> <span class="nav-text">评测用例规模与约定</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BF%90%E8%A1%8C%E9%99%90%E5%88%B6-2"><span class="nav-number">3.6.</span> <span class="nav-text">运行限制</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E8%A7%A3-2"><span class="nav-number">3.7.</span> <span class="nav-text">题解</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E8%B7%91%E6%AD%A5%E9%94%BB%E7%82%BC"><span class="nav-number">4.</span> <span class="nav-text">跑步锻炼</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0-3"><span class="nav-number">4.1.</span> <span class="nav-text">题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BF%90%E8%A1%8C%E9%99%90%E5%88%B6-3"><span class="nav-number">4.2.</span> <span class="nav-text">运行限制</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E8%A7%A3-3"><span class="nav-number">4.3.</span> <span class="nav-text">题解</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%B0%8F%E6%98%8E%E7%9A%84%E5%BD%A9%E7%81%AF-%E7%AE%80%E5%8D%95"><span class="nav-number">5.</span> <span class="nav-text">小明的彩灯(简单)</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0-4"><span class="nav-number">5.1.</span> <span class="nav-text">题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0-2"><span class="nav-number">5.2.</span> <span class="nav-text">输入描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0-2"><span class="nav-number">5.3.</span> <span class="nav-text">输出描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%85%A5%E8%BE%93%E5%87%BA%E6%A0%B7%E4%BE%8B-2"><span class="nav-number">5.4.</span> <span class="nav-text">输入输出样例</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E7%A4%BA%E4%BE%8B-1-1"><span class="nav-number">5.4.1.</span> <span class="nav-text">示例 1</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BF%90%E8%A1%8C%E9%99%90%E5%88%B6-4"><span class="nav-number">5.5.</span> <span class="nav-text">运行限制</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E8%A7%A3-4"><span class="nav-number">5.6.</span> <span class="nav-text">题解</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%B0%8F%E6%98%8E%E7%9A%84%E8%83%8C%E5%8C%851-dp"><span class="nav-number">6.</span> <span class="nav-text">小明的背包1(dp)</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0-5"><span class="nav-number">6.1.</span> <span class="nav-text">题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0-3"><span class="nav-number">6.2.</span> <span class="nav-text">输入描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0-3"><span class="nav-number">6.3.</span> <span class="nav-text">输出描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%85%A5%E8%BE%93%E5%87%BA%E6%A0%B7%E4%BE%8B-3"><span class="nav-number">6.4.</span> <span class="nav-text">输入输出样例</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E7%A4%BA%E4%BE%8B-1-2"><span class="nav-number">6.4.1.</span> <span class="nav-text">示例 1</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BF%90%E8%A1%8C%E9%99%90%E5%88%B6-5"><span class="nav-number">6.5.</span> <span class="nav-text">运行限制</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E8%A7%A3-5"><span class="nav-number">6.6.</span> <span class="nav-text">题解</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E8%B5%B0%E8%BF%B7%E5%AE%AB-BFS"><span class="nav-number">7.</span> <span class="nav-text">走迷宫(BFS)</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0-6"><span class="nav-number">7.1.</span> <span class="nav-text">题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0-4"><span class="nav-number">7.2.</span> <span class="nav-text">输入描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0-4"><span class="nav-number">7.3.</span> <span class="nav-text">输出描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%85%A5%E8%BE%93%E5%87%BA%E6%A0%B7%E4%BE%8B-4"><span class="nav-number">7.4.</span> <span class="nav-text">输入输出样例</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E7%A4%BA%E4%BE%8B-1-3"><span class="nav-number">7.4.1.</span> <span class="nav-text">示例 1</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BF%90%E8%A1%8C%E9%99%90%E5%88%B6-6"><span class="nav-number">7.5.</span> <span class="nav-text">运行限制</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E8%A7%A3-6"><span class="nav-number">7.6.</span> <span class="nav-text">题解</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E8%93%9D%E6%A1%A5%E9%AA%91%E5%A3%AB-%E4%B8%AD%E7%AD%89"><span class="nav-number">8.</span> <span class="nav-text">蓝桥骑士(中等)</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0-7"><span class="nav-number">8.1.</span> <span class="nav-text">题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0-5"><span class="nav-number">8.2.</span> <span class="nav-text">输入描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0-5"><span class="nav-number">8.3.</span> <span class="nav-text">输出描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%85%A5%E8%BE%93%E5%87%BA%E6%A0%B7%E4%BE%8B-5"><span class="nav-number">8.4.</span> <span class="nav-text">输入输出样例</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E7%A4%BA%E4%BE%8B-1-4"><span class="nav-number">8.4.1.</span> <span class="nav-text">示例 1</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BF%90%E8%A1%8C%E9%99%90%E5%88%B6-7"><span class="nav-number">8.5.</span> <span class="nav-text">运行限制</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E8%A7%A3-7"><span class="nav-number">8.6.</span> <span class="nav-text">题解</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E8%93%9D%E6%A1%A5%E4%BE%A6%E6%8E%A2-%E4%B8%AD%E7%AD%89"><span class="nav-number">9.</span> <span class="nav-text">蓝桥侦探(中等)</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0-8"><span class="nav-number">9.1.</span> <span class="nav-text">题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0-6"><span class="nav-number">9.2.</span> <span class="nav-text">输入描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0-6"><span class="nav-number">9.3.</span> <span class="nav-text">输出描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%85%A5%E8%BE%93%E5%87%BA%E6%A0%B7%E4%BE%8B-6"><span class="nav-number">9.4.</span> <span class="nav-text">输入输出样例</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E7%A4%BA%E4%BE%8B-1-5"><span class="nav-number">9.4.1.</span> <span class="nav-text">示例 1</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BF%90%E8%A1%8C%E9%99%90%E5%88%B6-8"><span class="nav-number">9.5.</span> <span class="nav-text">运行限制</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E8%A7%A3-8"><span class="nav-number">9.6.</span> <span class="nav-text">题解</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E9%94%BB%E9%80%A0%E5%85%B5%E5%99%A8"><span class="nav-number">10.</span> <span class="nav-text">锻造兵器</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0-9"><span class="nav-number">10.1.</span> <span class="nav-text">题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0-7"><span class="nav-number">10.2.</span> <span class="nav-text">输入描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0-7"><span class="nav-number">10.3.</span> <span class="nav-text">输出描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%85%A5%E8%BE%93%E5%87%BA%E6%A0%B7%E4%BE%8B-7"><span class="nav-number">10.4.</span> <span class="nav-text">输入输出样例</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E7%A4%BA%E4%BE%8B-1-6"><span class="nav-number">10.4.1.</span> <span class="nav-text">示例 1</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BF%90%E8%A1%8C%E9%99%90%E5%88%B6-9"><span class="nav-number">10.5.</span> <span class="nav-text">运行限制</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E8%A7%A3-9"><span class="nav-number">10.6.</span> <span class="nav-text">题解</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97"><span class="nav-number">11.</span> <span class="nav-text">最长公共子序列</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0-10"><span class="nav-number">11.1.</span> <span class="nav-text">题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0-8"><span class="nav-number">11.2.</span> <span class="nav-text">输入描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0-8"><span class="nav-number">11.3.</span> <span class="nav-text">输出描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%85%A5%E8%BE%93%E5%87%BA%E6%A0%B7%E4%BE%8B-8"><span class="nav-number">11.4.</span> <span class="nav-text">输入输出样例</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E7%A4%BA%E4%BE%8B-1-7"><span class="nav-number">11.4.1.</span> <span class="nav-text">示例 1</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BF%90%E8%A1%8C%E9%99%90%E5%88%B6-10"><span class="nav-number">11.5.</span> <span class="nav-text">运行限制</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E8%A7%A3-10"><span class="nav-number">11.6.</span> <span class="nav-text">题解</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%B0%8F%E6%98%8E%E7%9A%84%E8%A1%A3%E6%9C%8D"><span class="nav-number">12.</span> <span class="nav-text">小明的衣服</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0-11"><span class="nav-number">12.1.</span> <span class="nav-text">题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0-9"><span class="nav-number">12.2.</span> <span class="nav-text">输入描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0-9"><span class="nav-number">12.3.</span> <span class="nav-text">输出描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BE%93%E5%85%A5%E8%BE%93%E5%87%BA%E6%A0%B7%E4%BE%8B-9"><span class="nav-number">12.4.</span> <span class="nav-text">输入输出样例</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E7%A4%BA%E4%BE%8B-1-8"><span class="nav-number">12.4.1.</span> <span class="nav-text">示例 1</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BF%90%E8%A1%8C%E9%99%90%E5%88%B6-11"><span class="nav-number">12.5.</span> <span class="nav-text">运行限制</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E8%A7%A3-11"><span class="nav-number">12.6.</span> <span class="nav-text">题解</span></a></li></ol></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="君不见"
      src="/xlrblog/images/avatar.gif">
  <p class="site-author-name" itemprop="name">君不见</p>
  <div class="site-description" itemprop="description">君不见，黄河之水天上来，奔流到海不复回。</div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/xlrblog/archives/">
        
          <span class="site-state-item-count">50</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
        <span class="site-state-item-count">9</span>
        <span class="site-state-item-name">分类</span>
      </div>
      <div class="site-state-item site-state-tags">
        <span class="site-state-item-count">25</span>
        <span class="site-state-item-name">标签</span>
      </div>
  </nav>
</div>
  <div class="links-of-author motion-element">
      <span class="links-of-author-item">
        <a href="https://github.com/decxlr" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;decxlr" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
  </div>



      </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

        

<div class="copyright">
  
  &copy; 
  <span itemprop="copyrightYear">2023</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">君不见</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://pisces.theme-next.org/" class="theme-link" rel="noopener" target="_blank">NexT.Pisces</a> 强力驱动
  </div>

        








      </div>
    </footer>
  </div>

  
  <script src="/xlrblog/lib/anime.min.js"></script>
  <script src="/xlrblog/lib/velocity/velocity.min.js"></script>
  <script src="/xlrblog/lib/velocity/velocity.ui.min.js"></script>

<script src="/xlrblog/js/utils.js"></script>

<script src="/xlrblog/js/motion.js"></script>


<script src="/xlrblog/js/schemes/pisces.js"></script>


<script src="/xlrblog/js/next-boot.js"></script>




  




  
<script src="/xlrblog/js/local-search.js"></script>













  

  

</body>
</html>
